package com.c2b.algorithm.leetcode.base;

import java.util.LinkedList;
import java.util.Queue;

/**
 * <a href="https://leetcode.cn/problems/minimum-depth-of-binary-tree/">二叉树的最小深度(Minimum Depth of Binary Tree)</a>
 * <p>
 * 给定一个二叉树，找出其最小深度。
 * 最小深度是从根节点到最近叶子节点的最短路径上的节点数量。
 * 说明：叶子节点是指没有子节点的节点。
 * </p>
 * <pre>
 * 示例 1：
 *      输入：root = [3,9,20,null,null,15,7]
 *      输出：2
 *
 * 示例 2：
 *      输入：root = [2,null,3,null,4,null,5,null,6]
 *      输出：5
 * </pre>
 * <b>提示： </b>
 * <ul>
 *     <li>树中节点数的范围在 [0, 10^5] 内</li>
 *     <li>-1000 <= Node.val <= 1000</li>
 * </ul>
 *
 * @author c2b
 * @since 2023/5/11 13:25
 */
public class LC0111MinDepth_S {

    public int minDepth(TreeNode root) {
        if (root == null) {
            return 0;
        }
        //1.左孩子和有孩子都为空的情况，说明到达了叶子节点，直接返回1即可
        if (root.left == null && root.right == null) {
            return 1;
        }
        //2.如果左孩子和右孩子其中一个为空，那么需要返回比较大的那个孩子的深度
        int min_Depth = Integer.MAX_VALUE;
        if (root.left != null) {
            min_Depth = Math.min(min_Depth, minDepth(root.left));
        }
        if (root.right != null) {
            min_Depth = Math.min((min_Depth), minDepth(root.right));
        }
        //3.左右孩子都不为空，返回最小深度+1即可
        return min_Depth + 1;
    }

    public int minDepthByBFS(TreeNode root) {
        if (root == null) {
            return 0;
        }
        Queue<NodeInfo> queue = new LinkedList<>();
        queue.offer(new NodeInfo(root, 1));
        while (!queue.isEmpty()) {
            NodeInfo nodeInfo = queue.poll();
            TreeNode currNode = nodeInfo.node;
            int currDepth = nodeInfo.depth;
            if (currNode.left == null && currNode.right == null) {
                return currDepth;
            }
            if (currNode.left != null) {
                queue.offer(new NodeInfo(currNode.left, currDepth + 1));
            }
            if (currNode.right != null) {
                queue.offer(new NodeInfo(currNode.right, currDepth + 1));
            }
        }
        return 0;
    }

    static class NodeInfo {
        TreeNode node;
        int depth;

        public NodeInfo(TreeNode node, int depth) {
            this.node = node;
            this.depth = depth;
        }
    }

    public static void main(String[] args) {
        TreeNode node = new TreeNode(1);
        node.left = new TreeNode(2);
        node.left.left = new TreeNode(3);
        LC0111MinDepth_S lc0111MinDepth_s = new LC0111MinDepth_S();
        System.out.println(lc0111MinDepth_s.minDepth(node));
    }
}
